吴师兄学算法

# LeetCode 232、用栈实现队列

# 一、题目描述

请你仅使用两个栈实现先入先出队列。

队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：

实现 MyQueue 类：

  • void push(int x)将元素 x 推到队列的末尾
  • int pop() 从队列的开头移除并返回元素
  • int peek() 返回队列开头的元素
  • boolean empty()如果队列为空，返回 True ；否则，返回 False

# 二、题目解析

# 入队操作

如果是栈的插入操作，那我们可以把元素都先插入到 stackIn 中，也就实现了队列的 入队操作 。

# 出队操作

  • 当 stackOut 中不为空时，直接操作，此时在 stackOut 中的栈顶元素是最先进入队列的元素，返回该元素即可；
  • 如果 stackOut 为空且 stackIn 不为空，首先需要把 stackIn 中的元素逐个弹出并压入到 stackOut 中，然后返回 stackOut 的栈顶元素即可。

# 三、参考代码

# 1、Java 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 用栈实现队列 （ LeetCode 232 ）:https://leetcode-cn.com/problems/implement-queue-using-stacks/
class MyQueue {
    // 首先定义好两个栈

    // 一个栈叫做 stackIn，负责进栈操作，相当于队列 queue 中的入队操作
    Stack<Integer> stackIn;
    // 一个栈叫做 stackOut，负责出栈操作，相当于队列 queue 中的出队操作
    Stack<Integer> stackOut;
    
    public MyQueue() {
        // 在这个函数中初始化两个栈，传入的参数为空，返回也为空

        // 初始化 stackIn
        stackIn = new Stack<>();
        // 初始化 stackOut
        stackOut = new Stack<>();
    }
    
    
    public void push(int x) {
        // 新添加的元素添加到 stackIn 中
        stackIn.push(x);
    }
    
    public int pop() {

        // 如果 stackOut 为空，首先需要将 stackIn 中的所有元素添加到 stackOut 中
        // 注意 stackIn 是栈，栈的性质是先进后出，后进先出，所以是不断的将 stackIn 中的栈顶元素添加进 stackOut 中
        if (stackOut.isEmpty()) {
            // 通过 while 循环将 stackIn 中的所有元素都取出
            while (!stackIn.isEmpty()) {
                // stackOut 不断的添加 stackIn 的栈顶元素
                stackOut.push(stackIn.pop());
            }
        }
        // 此时，stackIn 已经为空，直接「移除」 stackOut 的栈顶元素
        return stackOut.pop();
    }
    
    
    public int peek() {

        // peek 和 pop 的区别在于是返回栈顶元素而非删除栈顶元素
        // 如果 stackOut 为空，首先需要将 stackIn 中的所有元素添加到 stackOut 中
        // 注意 stackIn 是栈，栈的性质是先进后出，后进先出，所以是不断的将 stackIn 中的栈顶元素添加进 stackOut 中
        if (stackOut.isEmpty()) {
            // 通过 while 循环将 stackIn 中的所有元素都取出
            while (!stackIn.isEmpty()) {
                // stackOut 不断的添加 stackIn 的栈顶元素
                stackOut.push(stackIn.pop());
            }
        }

        // peek 和 pop 的区别在于是返回栈顶元素而非删除栈顶元素
        // 此时，stackIn 已经为空，直接「返回」 stackOut 的栈顶元素
        return stackOut.peek();

    }
    
    public boolean empty() {
        // 队列是否为空，判断 stackIn 和 stackOut 是否同时不存在元素
        return stackIn.isEmpty() && stackOut.isEmpty();
    }
}

# **2、**C++ 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 用栈实现队列 （ LeetCode 232 ）:https://leetcode-cn.com/problems/implement-queue-using-stacks/
class MyQueue {
public:
 // 首先定义好两个栈

    // 一个栈叫做 stackIn，负责进栈操作，相当于队列 queue 中的入队操作
    stack<int> stackIn;
    // 一个栈叫做 stackOut，负责出栈操作，相当于队列 queue 中的出队操作
    stack<int> stackOut;
    
    MyQueue() {
 
    }
    
    
    void push(int x) {
        // 新添加的元素添加到 stackIn 中
        stackIn.push(x);
    }
    
    int pop() {

        // 如果 stackOut 为空，首先需要将 stackIn 中的所有元素添加到 stackOut 中
        // 注意 stackIn 是栈，栈的性质是先进后出，后进先出，所以是不断的将 stackIn 中的栈顶元素添加进 stackOut 中
        if (stackOut.empty()){
            // 通过 while 循环将 stackIn 中的所有元素都取出
            while (!stackIn.empty()) {
                // stackOut 不断的添加 stackIn 的栈顶元素
                int pop = stackIn.top();

                stackIn.pop();

                stackOut.push(pop);
            }
        }
        // 此时，stackIn 已经为空，直接「移除」 stackOut 的栈顶元素

        int pop = stackOut.top();

        stackOut.pop();

        return pop;
    }
    
    
    int peek() {

        // peek 和 pop 的区别在于是返回栈顶元素而非删除栈顶元素
        // 如果 stackOut 为空，首先需要将 stackIn 中的所有元素添加到 stackOut 中
        // 注意 stackIn 是栈，栈的性质是先进后出，后进先出，所以是不断的将 stackIn 中的栈顶元素添加进 stackOut 中
        if (stackOut.empty()) {
            // 通过 while 循环将 stackIn 中的所有元素都取出
            while (!stackIn.empty()) {
                // stackOut 不断的添加 stackIn 的栈顶元素
                int pop = stackIn.top();

                stackIn.pop();

                stackOut.push(pop);
            }
        }

        // peek 和 pop 的区别在于是返回栈顶元素而非删除栈顶元素
        // 此时，stackIn 已经为空，直接「返回」 stackOut 的栈顶元素
        return stackOut.top();
    
    }
    
    bool empty() {
        // 队列是否为空，判断 stackIn 和 stackOut 是否同时不存在元素
        return stackIn.empty() && stackOut.empty();
    }
};

# 3、Python 代码

# 登录 AlgoMooc 官网获取更多算法图解
# https://www.algomooc.com
# 作者：程序员吴师兄
# 代码有看不懂的地方一定要私聊咨询吴师兄呀
# 用栈实现队列 （ LeetCode 232 ）:https://leetcode-cn.com/problems/implement-queue-using-stacks/
class MyQueue:
    def __init__(self):
        # 一个栈叫做 stackIn，负责进栈操作，相当于队列 queue 中的入队操作
        self.stackIn = []
        # 一个栈叫做 stackOut，负责出栈操作，相当于队列 queue 中的出队操作
        self.stackOut = []


    def push(self, x: int) -> None:
        # 新添加的元素添加到 stackIn 中
        self.stackIn.append(x)


    def pop(self) -> int:
        # 如果 stackOut 为空，首先需要将 stackIn 中的所有元素添加到 stackOut 中
        #注意 stackIn 是栈，栈的性质是先进后出，后进先出，所以是不断的将 stackIn 中的栈顶元素添加进 stackOut 中
        if not self.stackOut:
            # 通过 while 循环将 stackIn 中的所有元素都取出
            while self.stackIn:
                # stackOut 不断的添加 stackIn 的栈顶元素
                self.stackOut.append(self.stackIn.pop())
        # 此时，stackIn 已经为空，直接「移除」 stackOut 的栈顶元素
        return self.stackOut.pop()


    def peek(self) -> int:
        # peek 和 pop 的区别在于是返回栈顶元素而非删除栈顶元素
        # 如果 stackOut 为空，首先需要将 stackIn 中的所有元素添加到 stackOut 中
        # 注意 stackIn 是栈，栈的性质是先进后出，后进先出，所以是不断的将 stackIn 中的栈顶元素添加进 stackOut 中
        if not self.stackOut:
            # 通过 while 循环将 stackIn 中的所有元素都取出
            while self.stackIn:
                # stackOut 不断的添加 stackIn 的栈顶元素
                self.stackOut.append(self.stackIn.pop())

        # peek 和 pop 的区别在于是返回栈顶元素而非删除栈顶元素
        # 此时，stackIn 已经为空，直接「返回」 stackOut 的栈顶元素
        return self.stackOut[-1]


    def empty(self) -> bool:
        # 队列是否为空，判断 stackIn 和 stackOut 是否同时不存在元素
        return not self.stackIn and not self.stackOut

← LeetCode 349、两个数组的交集 →